This invention relates in general to an automatic computer controlled technique for matching a set of points in a reference file record (hereinafter "File") against a set of points in a subject or search record (hereinafter "Search"), wherein each of the File and Search points have values associated with certain predetermined parameters. More particularly, this invention relates to a fingerprint matcher in which the positional parameters of a set of minutia points in a File are compared against the positional parameters of a set of Search minutia points to determine whether or not it sufficiently matches so that the Search subject can be verified.
Fingerprint matcher mechanisms are known. One such Matcher is described in Wegstein, J. H., The M-40 Fingerprint Matcher, National Bureau of Standards Technical Note 878, U.S. Government Printing Office, Washington, D.C. 1975. The matcher mechanism described in the Wegstein reference employs the position of each File minutia and Search minutia in X and Y coordinates and the angular value in degrees. As described in Wegstein, each File point is compared with each Search point, in each of these X,Y and angle parameters so as to provide displacement values for a difference table. A difference table is a table in which each entry is a comparison of a Search point against a File point. The table includes the displacement between the two points in the X direction, the displacement between the two points in the Y direction and may also include the angular displacement between the two minutia points being compared. A plot of the X displacement values and the Y displacement values creates a difference plane.
Certain clusters of points in the difference table are used to provide an indication of the extent to which the Search fingerprint might be displaced or rotated relative to the fingerprint from which the set of File points was obtained. Certain figures of merit or matching scores are obtained. Only if the matching score exceeds certain thresholds, is the Search fingerprint deemed to correspond with the File fingerprint.
A further improved matcher mechanism is described in Wegstein, Joseph H., Automated Fingerprint Identification System, National Bureau of Standards publication 500-89, issued February 1982.
The utility of a matcher is a function of the speed with which it operates and its error rate. There are two types of error. A type I error is the failure to verify a match when the subject finger is indeed the same as the finger from which the File was obtained. This is an incorrect rejection in an access system. A type II error is the verification of a subject fingerprint which in fact is not the same as the fingerprint from which the File was made. This is an incorrect admission in an access system.
The value of any matcher mechanism is the extent to which the matcher contributes to increasing the speed of operation of a verification system, to reducing type I errors and to reducing type II errors.
There is a trade off between these three operating characteristics and the amount of distortion and lack of registration which can be tolerated. A major, if not the major, problem in matching fingerprint derived data is due to the plasticity of the finger. The resultant variation in finger impression from time to time results in substantial image variation.
Accordingly, it is a purpose of this invention to provide an enhanced matcher in which an improved trade off is obtained between the characteristics of speed, type I error, type II error, and ability to accept distortion and lack of registration.
It helps to keep in mind the significance of certain terminology. In particular, the following terminology recurs throughout the disclosure.
The Matcher device of this invention involves a number of major components which operate together to provide the total decision making in identification that is appropriately termed matching. More particularily, the Matcher has four separately scaled comparator segments which are integrated so as to provide a variable scale matching function. The Matcher also includes a scorer mechanism. However for the Matcher to operate to provide decision making, it must also have storage for the File minutia points and a storage for the Search minutia points. It is a combination of all of these components that constitutes the Matcher.
The difference table includes X differential values and Y differential values. The difference plane is one on which the X differential and Y differential values of the difference table are plotted. The difference table (D.T. herein) and the difference plane have to be kept in mind as distinct from the image plane on which the minutia points appear. Thus an entry on the difference plane is a point (a) whose X coordinate represents the difference along the X axis of the image plane between a given file point and a given search point and (b) whose Y coordinate represents the difference along the Y axis of the image plane between that file point and search point.
The term "Q" is used in different contexts with different sub-scripts to generally refer to how tightly various points are bound to one another. It is a measurement of relative proximity. Is is roughly analogous to spatial peaking, with reference to space on the difference plane not on the image plane. The term Qc will refer to a measure of how close two points on the difference plane are to one another. The term Qs will provide a measure of how close a particular point on the difference plane is to all the rest of the points in the difference plane. And the measurement Qt will provide an indication of how close to each other are all of the points on the difference plane. But generically this measurement of proximity on the difference plane will be referred to as Q. It should be noted that the term QT is used herein, particularly in the FIGS., interchangeably with Qt to mean the same thing.
The minutia referred to herein are the classical minutia, namely line endings and line bifurcations. These are the known type of minutia which are traditionally used to identify a fingerprint. The location of each minutia on the image plane is indicated in X and Y coordinates and is represented by the picture element (pixel) which contains the end point of the minutia. The angle of the minutia in the image plane is also employed to identify the minutia and can be employed as part of the matching mechanism. The embodiment of the invention described herein employs that angle only in terms of an initial qualification criteria for entry on the difference table. The angle is not thereafter used in the embodiment described although the matcher mechanism can be generalized to include angle differential values in the difference table as a contributor to the Q factor.